1. The Field of the Invention
The present invention relates to methods for efficiently generating a selection representation for items in tree-type data structures. More particularly, the present invention relates to systems and methods for using selection representations in logical groupings in a tree structure.
2. The Relevant Technology
Tree structures are used extensively in computer science and telecommunications because of the organized manner in which the hierarchical nature of a structure can be depicted in graphical form. The elements of the tree structure have certain terminology. The elements themselves are called “nodes.” The lines connecting elements are called “branches.” The starting node is often called the “root.” A node is a “parent” of another node if it is one step higher in the hierarchy. “Sibling” nodes share the same parent node and are referred to as children of the parent node. Nodes without children are called “end-nodes” or “leaves.”
Tree structures are used to depict all kinds of taxonomic knowledge, such as family trees, the Evolutionary tree, the grammatical structure of a language, the way web pages are logically ordered in a web site, etc. In a tree structure there is only one path from any point to any other point. Thus, each element can be defined by a particular path.
In a computer science environment, when a user is allowed to select various elements in a tree structure, the user must explicitly call out which items they choose to select. As can be appreciated, for a very large tree structure, the selection list created can become extensive. Furthermore, because tree structures can have multiple tiers of parent/children nodes, the user may want to select a parent node, but not select one or more children of the parent. This can result in extensive selection lists to accommodate selection and/or deselection of parent, children, grandchildren, great grandchildren nodes, etc.
FIG. 1 illustrates an exemplary selection list for use with a backup system. The user has selected certain files to be included in a backup. Each of the files or elements are represented by an explicit pathway so that a processor will know where in a file system to look for the element. In this exemplary hypothetical, the file system relates to files contained in the E:\ drive. Had the user wanted all of the files in the E drive to be backed up, it would be a simple matter for the selection system to simply list E:\. However, in the embodiment of FIG. 1, the user has determined that certain files are not to be backed up, and hence, the need to explicitly state all of the files that the user requests to be positively selected for saving. As can be seen, the selection list just for the E drive is extensive. When other drives are also considered, it is appreciated that the selection list can become extremely long depending on the number of files selected for backup.
Creating a selection list is further complicated because often for certain predetermined functions, such as in SQL or Exchange applications, particular files must be grouped together for various reasons, hereinafter referred to as a “group” or “grouping.” A user may want to perform a function (e.g., a backup or recovery) on a given item in a group without wanting to know what individual items comprise the group. Within this example, it might be detrimental to allow a user to perform a function on a given item that belongs to a group, without including the other items that comprise the group. Thus, when performing a function on groups, most applications require the group-specific items be grouped and separated from the items. The user, then, is presented with items and groups rather than the individual items that make up the groups. This protects the user from inadvertently damaging the groups via an erroneous function performed on an individual item when the other items of the group should also be taken into account.
Conventionally, when performing a function on the file system, a selection list of items must be generated for the selected/deselected items of the file system as well as for each group. The entire file system must then be filtered (i.e., enumerated recursively and each item compared) against each of these selection lists. This process may need to be repeated several times, depending on the number of groups that must be taken into account. Thus, such an operation can be performance-intensive, particularly, if there are many groups to be considered.